package tgipl3.medium.buildingBlocks;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class UserMainCodeV1
{
	//Assume following return types while writing the code for this question. 
	public static int[] output1;
	private static Cluster[][] plotClusters;
	private static int output1Ind = 0;
	
	private static class Cluster extends ArrayList<Node> implements Comparable<Cluster> {
		private static final long serialVersionUID = 1L;
		int canFill = 0, height = 0;
		static final int CAN_FILL_INFINITY = -1;
		public Cluster(Node node, int height) {
			add(node);
			this.height = height;
		}
		@Override
		public int compareTo(Cluster cluster) {
			return height - cluster.height;
		}
	}
	
	private static class Node {
		int row, col;
		public Node(int row, int col) {
			this.row = row;
			this.col = col;
		}
		public boolean equals(Object obj) {
			if(obj instanceof Node)
				return row == ((Node)obj).row && col == ((Node)obj).col;
			return false;
		}
		public String toString() {
			return "(" + row + ", " + col + ")";
		}
	}

	private static List<Cluster> getClusters(int[][] plot) {
		ArrayList<Cluster> clusters = new ArrayList<Cluster>();
		for(int i = 1; i < plot.length - 1; i++) {
			for(int j = 1; j < plot[i].length - 1; j++) {
				if(plot[i - 1][j] >= plot[i][j] && plot[i][j - 1] >= plot[i][j]
						&& plot[i][j + 1] >= plot[i][j] && plot[i + 1][j] >= plot[i][j]) {
					Cluster cluster = new Cluster(new Node(i, j), plot[i][j]);
					clusters.add(cluster);
					plotClusters[i][j] = cluster;
				}
			}
		}
		return clusters;
	}
	
	/**
	 * Merges second cluster into the first
	 * @param cluster1
	 * @param cluster2
	 */
	private static void mergeClusters(Cluster cluster1, Cluster cluster2) {
		cluster1.addAll(cluster2);
		cluster1.canFill = Math.min(cluster1.canFill, cluster2.canFill);
	}
	
	private static void expandCluster(List<Cluster> clusters, Cluster cluster, int[][] plot, Node node, int row, int col) {
		Node newNode = new Node(row, col);
		if(plot[node.row][node.col] >= plot[row][col]) {
			if(!cluster.contains(newNode)) {
				if(plotClusters[row][col] != null && plotClusters[row][col] != cluster) {
					mergeClusters(cluster, plotClusters[row][col]);
					clusters.remove(plotClusters[row][col]);
				} else
					cluster.add(newNode);
				plotClusters[row][col] = cluster;
			}
		} else {
			int newCanFill = plot[row][col] - plot[node.row][node.col];
			if(cluster.canFill == Cluster.CAN_FILL_INFINITY || newCanFill < cluster.canFill)
				cluster.canFill = newCanFill;
		}
	}
	
	private static boolean expandCluster(List<Cluster> clusters, Cluster cluster, int[][] plot) {
		cluster.canFill = Cluster.CAN_FILL_INFINITY;
		for(int i = 0; i < cluster.size(); i++) { // will this loop items added in the loop?
			Node node = cluster.get(i);
			if(node.row == 0 || node.row == plot.length - 1
					|| node.col == 0 || node.col == plot[0].length - 1) {
				// remove the cluster as the water overflows
				clusters.remove(cluster);
				return false;
			}
			expandCluster(clusters, cluster, plot, node, node.row - 1, node.col);
			expandCluster(clusters, cluster, plot, node, node.row, node.col - 1);
			expandCluster(clusters, cluster, plot, node, node.row, node.col + 1);
			expandCluster(clusters, cluster, plot, node, node.row + 1, node.col);
		}
		return true;
	}
	
	private static void fillCluster(Cluster cluster, int[][] plot) {
		int newHeight = cluster.height + cluster.canFill;
		for(Node node : cluster)
			plot[node.row][node.col] = newHeight;
		cluster.height = newHeight;
		output1[output1Ind] += cluster.canFill * cluster.size();
	}
	
	private static int[][] getPlots(String tc) {
		int cind = tc.indexOf(',');
		int l = Integer.parseInt(tc.substring(0, cind));
		tc = tc.substring(cind + 1);
		cind = tc.indexOf(',');
		int b = Integer.parseInt(tc.substring(0, cind));
		tc = tc.substring(cind + 3, tc.length() - 2);
		int p[][] = new int[l][b];
		String rows[] = tc.split("\\},\\{");
		for(int i = 0; i < rows.length; i++) {
			String elts[] = rows[i].split(",");
			for(int j = 0; j < elts.length; j++)
				p[i][j] = Integer.parseInt(elts[j]);
		}
		return p;
	}
	
	public static void GetWaterLevel(int input1,String input2)
	{
		input2 = input2.substring(1, input2.length() - 1);
		String tcs[] = input2.split("\\),\\(");
		output1 = new int[tcs.length];
		for(String tc : tcs) {
			int p[][] = getPlots(tc);
			plotClusters = new Cluster[p.length][p[0].length];
			List<Cluster> clusters = getClusters(p);
			while(clusters.size() > 0) {
				Collections.sort(clusters); // need not be sorted every time, we can shift the position of the cluster being modified
				Cluster minCluster = clusters.get(0);
				if(expandCluster(clusters, minCluster, p))
					fillCluster(minCluster, p);
			}
			output1Ind++;
		}
	}
	
	public static void main(String[] args) throws IOException
	{
		String[] inputs = "1:(3,6,{{3,3,4,4,4,2},{3,1,3,2,1,4},{7,3,1,6,4,1}})".split(":");
		GetWaterLevel(Integer.parseInt(inputs[0]), inputs[1]);
		System.out.println(Arrays.toString(output1));
	}
}